package com.iran;

import java.util.Arrays;

/**
 * 小顶堆
 */
public class HeapSortMin {
    static int[] arr;
    public static void main(String[] args) {
        HeapSortMin heapSortMin = new HeapSortMin();
        int[] arr = {0,23,45,9,40,73,12,49,423,122,33,44,55,66,77,88,99,101,102,133,144};//第0位代表数组长度
        arr[0] = arr.length-1;
        heapSortMin.arr = arr;
        heapSort(arr);
    }
    static void heapSort(int[] arr){
        //建堆
        for (int i=(arr.length-1)/2;i>0;i--){
            heapAdjust(arr,i,arr.length-1);
        }
        //调整
        for (int k=arr.length-1;k>0;k--){
            int min = arr[1];//最小值
            arr[1] = arr[k];
            arr[k] = min;//与最后一位叶子节点调换位置
            heapAdjust(arr,1,k-1);
        }
        Arrays.stream(arr).forEach(System.out::println);
    }
    static void heapAdjust(int[] arr,int s,int m){
        int unChildNode = arr[s];//父节点值
        for (int j=s*2;j<=m;j=2*s){
            if (j<m&&arr[j]>arr[j+1] ){
                j++;
            }
            if (unChildNode<=arr[j]){
                break;
            }
            arr[s] = arr[j];
            s=j;
        }
        arr[s]=unChildNode;
    }
}
